home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 8958 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.1 KB

  1. Path: anvil.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: C library on computation of matrix determinants
  5. Date: 6 Mar 1996 15:03:14 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4hl5jiINNbom@anvil.ugrad.cs.ubc.ca>
  8. References: <wiedem01.4.000E6903@fsuni.rz.uni-passau.de>
  9. NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca
  10.  
  11. In article <wiedem01.4.000E6903@fsuni.rz.uni-passau.de>,
  12. WIEDEMANN CHRISTINE <wiedem01@fsuni.rz.uni-passau.de> wrote:
  13. >I'm looking for a library containing source codes on how to compute a 
  14. >determinant of a matrix. Does anybody know where to find such a library, 
  15. >source codes or algorithms on determinant computation.
  16.  
  17. One way to do this is to do Gaussian elimination on the matrix, while applying
  18. the same row operations to an identity matrix. Once you isolate the pivots, the
  19. determinant is just a product of the diagonal elements. As a bonus, if you
  20. carry through the operations, you get the matrix inverse.
  21.  
  22. The naive method of computing the determinant by recursive expansion of
  23. cofactors/minors yields exponential complexity, whereas Gaussian runs in cubic
  24. time in the rank of the matrix.
  25.  
  26. Thus the algorithm you are really looking for is one which reduces the matrix
  27. to triangular form, from which the determinant readily follows.
  28.  
  29. I wrote a C module a few years ago that does these kinds of things, but it is
  30. in archival storage, unfortunately!
  31.  
  32. Never mind, however---just find a good textbook on the subject of numerical
  33. analysis. The subject of reducing matrices is usually covered in detail. There
  34. are variations of the method, because there is some lattitude in choosing
  35. pivots in attempts to minimize errors. Gaussian elimination is sensitive to
  36. diagonal elements that are close to zero, since the presence of a true zero
  37. signals a matrix that is singular (determinant is zero), but it's difficult to
  38. distinguish between a actual non-zero value, and a perturbed zero value.
  39.  
  40. There is probably a better newsgroup to ask this question; perhaps something
  41. related to numerical analysis.
  42. -- 
  43.  
  44.